Time correlated data such as sounds, images, speech, etc. are by their nature analog (i.e. continuous). However, computers are, for the most part, digital (i.e. discrete). In order for a digital computer to process analog signals, the analog signals are first converted into digital signals which represent the analog signals. This is accomplished by repeatedly sampling the analog signals in short time intervals and converting each sampled value into a digital value. The resulting digital signal can then be processed by the digital computer. The processing of such digitized signals by a computer is known as digital signal processing.
Presently, digital signal processing is being applied to multimedia applications whereby text, audio, speech, video, data communications, and other time correlated data are integrated to create a more effective presentation of information. However, handling these applications in a real-time environment requires a large amount of processing power. The computer's Central Processing Unit (CPU) typically does not have the requisite processing power. In order to handle the load associated with operating these tasks in real-time, one or more dedicated digital signal processors (DSPs) are employed.
A DSP is designed to accept incoming samples at the average rate that the samples are being generated by an input process. The DSP then processes the input samples according to a computer program and produces outgoing signals at the average consumption rate of an output process. One efficient method for performing real-time processing on a DSP is known as frame-based processing. In frame-based processing, time is divided into a series of discrete units known as "frames," within which all the required signal processing for that frame is completed.
This is accomplished by dividing digital signals into groups which represent the same amount of time as a frame. For example, given that Compact Disc audio data runs at a rate of 44,100 samples per second and assuming a frame rate of 10 milliseconds (100 frames per second), there would be 441 samples per frame. During each frame, the corresponding program code, variables, and input samples are loaded into a high speed cache. From the cache, the input samples are then processed according to the tasks. Finally, the resulting output data is dumped into an output buffer to be used by an output process.
In a frame-based architecture, each of the tasks is typically linked or associated with one another through a data structure. An interrupt or other timing signal is generated and sent to the DSP at the beginning of each frame. This initiates the processing of the data structure, such that each task is sequentially executed within a frame.
One of the advantages of frame-based processing is that it reduces the task switching overhead. For example, given four tasks each handling a sample stream of 44,100 samples per second, if each task must be run once for every sample, you have a total of 4*44,100 or 176400 task switches in a second. By implementing frame-based processing running 100 frames per second and given the same four tasks, each of which run 100 times in a second, requires only 400 task switches per second. This reduces the task switching overhead by a factor of 441.
One major drawback with a frame-based system is increased latancy. A processing system that handles one sample at a time can respond in the next sample to a change in the input. In a frame-based system, a response takes two frames. This is because data is collected in one frame, processed in the next frame, and output in the following frame.
Another problem with frame-based systems is that, because each individual frame is of a fixed time duration, there exists only a certain, finite amount of processing time per frame. Consequently, when a number of tasks are being processed in real-time, it must be ensured that the frame's processing time is not exceeded. Otherwise, the real-time process will be disrupted in an unacceptable manner. Under certain circumstances, a frame's processing might be exceeded when executing the tasks to be processed during that frame. For instance, an unexpected aspect of one of the task's algorithms might cause that task to require more processing time, resulting in a frame overrun. Another example which might lead to a frame overrun is if a task is sensitive to input data, and the data has been corrupted or damaged. Indeed, an overloaded bus might deteriorate the system performance to a point whereby a frame overrun occurs. In some cases, such as debugging a program on a line-by-line basis, frame overruns are inevitable. Sometimes a task's algorithm might operate properly 99.9% of the time, but due to a defect, a particular command or data sequence results in an endless loop or an inordinate increase in processing time.
Ensuring that 100 percent of the frame's processing is not exceeded is relatively easy to implement if there is only one application running a single task. When the application is being written, the programmer can account for particular tasks and adjust the processing accordingly. In contrast, if a variety of multiple tasks are being installed and run by a number of different applications, a serious problem arises in determining whether there is enough processing power left in a particular frame for handling subsequent applications and/or tasks processing requests. Different hardware substantiations or configurations may also affect the processing load.
Thus, what is needed is an apparatus and method for determining 1) the processing time available within a frame when an additional task is about to be installed and 2) the worst-case processing time for that task. These two values can be compared to guarantee that when a task is installed, it can be fully executed within that frame. It would also be beneficial for the apparatus and method to be simple to implement, have low overhead, and also be dynamic (i.e., adaptive in real-time to the real environment).